The present invention relates generally to communications networks and more particularly, to a method and apparatus for monitoring the rate of one or more connections of message, cell or frame traffic in such networks.
In many instances, it is necessary or desirable to measure the rate of transmission of a message stream at a specific measurement point in a communications network. Rates may be measured on the aggregate of several connections or at the level of individual connections. These rate measurements may in turn be used to determine the activity state of a connection, for instance for bandwidth allocation or feedback control purposes.
In the Asynchronous Transfer Mode (ATM) networking protocol, multiple classes of communications service have been standardized. The ATM Forum Traffic Management Working Group has defined five service categories for cell transmission which are distinguished by parameter sets used to describe source behaviour and quality of service (QoS) guarantees. The service categories are identified as constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR). Traffic management techniques such as flow control are used in communications networks to protect a network from congestion and to achieve network performance or utilization objectives. Flow control in the ABR service category is achieved by arranging for each source node of a network to send special resource management (RM) cells through the network. Each network entity or element, for instance a switch or a node in the network, may indicate its congestion status by writing into the RM cell. The RM cell is then forwarded on to the next network element in the data path. At the destination network element, the RM cell is turned back towards the source. The network entities in the backward data path may mark congestion information into the RM cell, which is ultimately received by the source. The source may then adjust its sending rate in response to the information contained in the received RM cell.
Various mechanisms can be used in order to achieve flow control in a network. These mechanisms can be classified broadly depending on the congestion monitoring criteria used and the feedback mechanism employed. The feedback mechanisms are either binary in nature or may calculate an explicit rate of transmission. In binary flow control methods, a source of message transmission may receive feedback information to either increase its rate of transmission or decrease its rate of transmission depending on the instantaneous traffic flows at each contention point in the network. In explicit rate (ER) feedback schemes, an actual explicit rate of transmission for the connection will be determined by the network element or node and this information will be sent to the source of message transmission. This explicit rate of transmission is calculated at periodic intervals which may not necessarily be equal to one cell time. Examples of ER mechanisms known to those skilled in this art are the Enhanced Proportional Rate Control Algorithm (EPRCA) and two congestion avoidance schemes, namely Explicit Rate Indication for Congestion Avoidance (ERICA) and Congestion Avoidance Using Proportional Control (CAPC). While it is generally thought that binary feedback schemes may sometimes suffer from unfairness problems depending on the network topology and on the source and destination behaviour employed, the objective of ER algorithms is to allocate bandwidth at each link in the network so that the link is fully utilized and a fair distribution of bandwidth between connections is achieved.
Typically, basic rate measurements in communications networks are conducted as follows. Upon the arrival of a cell at a measurement point the current time is recorded, for instance by means of a time stamp. The time stamp associated with the arrival of the last preceding cell is then subtracted from the current time. This measure of inter-cell timing is extremely noisy, and is very sensitive to cell delay variation induced by buffering and cell scheduling throughout the network. As explained below, it is usual that some type of signal processing must be performed on the raw timing measurements in order to arrive at an estimate of the transmission rate for a given connection.
Known network architectures will generally apply some form of traffic shaping at the source of message transmission so as to enforce a constant cell inter-departure time. However, as a result of the effect of various queuing delays encountered along the message path, random variations to the intended inter-departure times will likely be introduced. These random variations may be modelled as fixed times to which a noise quantity or jitter has been added. Thus, if m is the intended constant cell inter-departure time and X is the noise quantity associated with a particular rate measurement, the calculation of a per-connection rate thus consists of estimating m from a number of observations or samples of the cell inter-arrival times, as follows:
T(1)=m+X(1), T(2)=m+X(2),xe2x80x83xe2x80x83(1)
where T is a particular measurement of a cell inter-arrival time.
In the available bit rate (ABR) service category of ATM networking, the mean rate of transmission from a source can be expected to change as a result of dynamic bandwidth allocation and feedback control. Therefore, a given source of message transmission may initially transmit at a mean rate associated with an inter-departure time m, but may be instructed during message transmission to transmit at a higher rate associated with a cell inter-departure time w. In this scenario, the inter-arrival times become:
T(1)=m+X(1), T(2)=m+X(2), . . . , T(n)=m+X(n), T(n+1)=w+X(n+1),
T(n+2)=w+X(n+2),xe2x80x83xe2x80x83(2)
where between the nth and (n+1)th cells a change in rate has occurred. One of the problems encountered in rate measurements is that of formulating a method of measurement which can detect such transitions in the mean rate of transmission.
Heretofore, three principal rate measurement methods which are based upon corresponding filtering techniques have been utilized in the monitoring of transmission rates in communications networks. Generally, the rate R associated with a network connection is defined as the inverse of the inter-arrival time between two cells over a connection, provided the connection produces such cells without any jitter. As mentioned previously, all the connections in an ATM network can experience some jitter when traversing through a series of network nodes. Thus, rate measurement methods have to employ some type of averaging technique to smoothen this jitter. One can employ a low pass filter for such averaging. The three known methods of rate measurement which use a low pass filter can be broadly classified as rate filtering (RF) methods, time-interval filtering (TIF) methods and modified rate filtering (MRF) methods.
In typical rate filtering methods, a low pass filter is used to filter the inverse of cell inter-arrival times. The connection rate according to these methods is determined as follows:                               Rate          ⁡                      (            k            )                          =                                            (                              1                -                α                            )                        ·                          Rate              ⁡                              (                                  k                  -                  1                                )                                              +                      α            ·                          (                              1                                  Δ                  ⁢                                      xe2x80x83                                    ⁢                  t                                            )                                                          (        3        )            
where:
Rate(k) is the rate of the connection being monitored at the kth cell arrival point;
xcex94t is the inter-arrival time between the kth and kxe2x88x921th cells; and
xcex1 is the filter gain factor.
One technique of rate filtering is the finite impulse response (FIR) filter. In this technique, a weighted average is maintained over a constant number of most recent timing sample points. In general terms, the FIR filter as applied to input rate monitoring would assume the following form:
Rn=xcex2xc2x7Rnxe2x88x921+(1xe2x88x92xcex2)/xcex94txe2x80x83xe2x80x83(4)
where:
Rn is the new estimated rate at time n;
Rnxe2x88x921 is the previous estimated rate at time nxe2x88x921;
xcex2 is a pre-calculated constant controlling the weight of previous samples, typically set to 0.98; and
xcex94t is the elapsed time between the previous sample at time tnxe2x88x921 and the current sample at time tn.
It is generally thought that the FIR method is effective in measuring input rates for actively transmitting sources on a network. However, when a source becomes idle, it is necessary to detect that cell arrival has terminated at the point of measurement. In order to do so, a background process is usually required. The background process will cycle through all connections and compare the current time with that of the most recent cell arrival on a per connection basis. Subject to a predetermined criterion, one or more particular connections may be declared idle. For instance, a connection such as an ATM virtual circuit may be declared inactive when its transmission rate falls significantly below the minimum cell rate (MCR) of the connection.
In time-interval filtering methods, a low pass filter is again used. In these methods the low-pass filter is applied directly to the cell inter-arrival times as opposed to being applied to the inverse of the cell inter-arrival times as is the case with the rate filtering methods described above. The connection rate is determined as the inverse of this filtered inter-arrival time, as follows:
TI(k)=(1xe2x88x92xcex1)xc2x7TI(kxe2x88x921)+xcex1xc2x7xcex94txe2x80x83xe2x80x83(5)
                              Rate          ⁡                      (            k            )                          =                  1                      TI            ⁡                          (              k              )                                                          (        6        )            
where:
TI(k) is the filtered cell inter-arrival time;
Rate(k) is the rate of the connection at the kth cell arrival point;
xcex94t is the inter-arrival time between the kth and kxe2x88x921th cells; and
xcex1 is a filter gain factor.
One technique of time-interval filtering is the infinite impulse response filter (IIR). In the IIR methodology for rate measurement, a smoothed version of the inter-arrival cell times is derived. This smoothing is again achieved by means of a low pass filter. Specifically, the following expression can be used to implement the method:
xe2x80x83y(n+1)=(1xe2x88x92c)xc2x7y(n)+cxc2x7T(n+1)xe2x80x83xe2x80x83(7)
where:
y(n) is the estimate of the mean arrival time at the arrival of the nth cell;
y(n+1) is the filtered cell inter-arrival time;
c is a filter factor, such that 0 less than c less than 1; and
T(n+1) is the inter-arrival time between cells n and n+1.
In IIR methods the closer c is to a value of 0, the sharper will be the filter. When a change from an inter-arrival time of m to w takes place, the mean arrival times y will begin to track the new mean cell inter-arrival time w. The estimate of the arrival rate over a virtual connection (VC) according to this method is thus given by
VCrate=1/y(n)xe2x80x83xe2x80x83(8)
The IIR method described above is relatively easy to implement and requires storing only one number per measured connection. However, the above calculations must be done at every cell arrival at the measurement point. As well, in order to detect a transition from an active state to an inactive state for a connection, background processing is used to check the current arrival time against the time of the last cell arrival. Where this difference is greater than a certain fixed threshold, the particular connection is declared inactive. For instance, if the calculated transmission rate VCrate for a connection is less than a fraction f of the minimum cell rate MCR, the connection may be declared inactive, i.e. where VCrate less than fxc2x7MCR. The first cell inter-arrival time (namely T(0)) can be used as the initial condition for the above filter.
Modified rate filtering methods are a variant of the rate filtering methods described above. In modified rate filtering methods, the connection rate is determined generally in the following manner:                               Rate          ⁡                      (            k            )                          =                                            (                              1                -                α                            )                        ·                          Rate              ⁡                              (                                  k                  -                  1                                )                                              +                      α            ·                          (                                                N                  -                  1                                                  Δ                  ⁢                                      xe2x80x83                                    ⁢                  T                                            )                                                          (        9        )            
where:
Rate(k) is the rate of the connection at the kth cell arrival point;
xcex94T is the inter-arrival time between the k+Nth and kth cells; and
xcex1 is once again a filter gain factor.
Thus, instead of using the inter-arrival time between every cell, modified rate filtering methods utilize the time to receive N cells instead.
More accurate known methods of input rate monitoring involve keeping track of the mean m(j) and variance Var(j) of the cell rate measurement over time, and using hypothesis testing for detecting rate changes. In turn, such hypothesis testing is also used to detect the inactivity of a connection. Hypothesis testing methods for input rate measurements typically assume that the distribution of the jitter X is nearly Gaussian and that the mean square variation of the jitter is nearly constant and is independent of the mean cell rate. If this assumption is correct, it can be shown that the probability of the inter-arrival time T being either greater than (1.95996s+m) or less than (xe2x88x921.95996s+m) is 5%, where s is the standard deviation of the jitter and m is the inter-arrival time. Thus, it can be declared that a change in transmission rate has occurred if a certain value of T falls outside this statistical range. This method assumes that the estimates of m and s are available. In what follows, three different examples of hypothesis testing methods are examined. The choice among the estimatory equations provided in Examples I, II or III below represents a trade-off between computational efficiency and the amount of storage required for variables and intermediate values.
With every cell arrival, the mean inter-arrival time, variance and standard deviation can be updated as:
m(j+1)=m(j)+(T(j)xe2x88x92m(j))/(j+1)xe2x80x83xe2x80x83(10)
Var(j+1)=(1xe2x88x921/j)xc2x7Var(j)+(j30 1)xc2x7(m(j+1)xe2x88x92m(j))2xe2x80x83xe2x80x83(11)
s(j)=Sqrt(Var(j+1))xe2x80x83xe2x80x83(12)
where:
Var(j) and Var(j+1) are the variances of the cell rate measurement after samples j and j+1, respectively,
m(j) and m(j+1) are the mean estimates of the cell rate measurement after samples j and j+1, respectively;
T(j) is the cell inter-arrival time of sample j, namely the current time less the time at which sample jxe2x88x921 was received;
s(j) is the standard deviation of the inter-arrival time of the measurement after j samples; and
Sqrt is the square root function.
This method requires memory storage only for the two most recent values of m(j) and the most recent Var(j) for each connection being monitored.
Alternatively, one can estimate m and s using sample quantiles. For a sample of n observations of a random variable t the value of the rth quantile (where 0xe2x89xa6r xe2x89xa61) for the variable corresponds to the observation that 100 r% of the observations are smaller than it. Thus, if T(1), T(2), . . . T(n) are the timing observations and T(n,1), T(n,2), . . . T(n,n) are the same values as arranged in ascending order, then the rth empirical quantile is T(n, Ceil(rn)), where Ceil is the ceiling function. The following provides an estimate of the mean m and the standard deviation s:
m(n)=0.3xc2x7T(n, Ceil(n/3))+0.4xc2x7T(n, Ceil(n/2))+0.3.xc2x7T(n, Ceil(2n/3))xe2x80x83xe2x80x83(13)
s(n)=0.7412898xc2x7[T(n, Ceil(0.75n))xe2x88x92T(n, Ceil(0.25n))]xe2x80x83xe2x80x83(14)
The greater the number of samples n which are collected, the better will be the estimate of the quantiles that are achieved.
As an approximation to the recursions of Example I above, one can calculate the following filtered values instead:
xe2x80x83m(r+1)=(1xe2x88x92e)xc2x7m(r)+exc2x7T(r+1)xe2x80x83xe2x80x83(15)
Var(r+1)=(1xe2x88x92c)xc2x7Var(r)+cxc2x7(T(r+1)xe2x88x92m(r))2xe2x80x83xe2x80x83(16)
where 0 less than e less than 1 and 0 less than c less than 1. To avoid the implementation of a divide operation, the first recursion of equation (15) above approximately tracks the mean of T(r) and the second recursion of equation (16) above approximately tracks the variance of T(r), so that the extent of deviation of T(r) is approximately tracked by Sqrt (Var(r)). Both recursions can be reset when a change in the transmission rate has been detected. Thus, the measurement process is restarted by assigning the inter-arrival time between the last two cell samples as the value of m(0), and the value of 0 is assigned to Var(0). This restart initialization of the values of m(0) and Var(0) is also applicable to the estimatory method of Example I above.
Several shortcomings associated with known rate algorithms as described above include the fact that some of these methods are sensitive to jitter in the input sample. As well, in the known methods of rate measurement, additional state information may be required per measured connection, in that background processing is utilized in order to determine whether a particular connection is inactive. When such background processing is required, the background task will need access to the same memory as used by the rate measurement process. This may complicate the implementation of rate measurement as a time-shared or dual-ported memory may be required to support the background task. Many of the methods also produce an over estimation of bandwidth, such that the sum of estimated bandwidths across all connections often exceeds the total actual link bandwidth. Other known rate estimation methods may respond to rate changes in a non-linear manner with over-shooting of the actual rate of transmission (see FIG. 5). For instance, when rate increases occur, cell samples will arrive faster with rate calculations being performed more rapidly. This results in nonlinear tracking of the actual rate with over-shooting since the calculated rate will be more heavily influenced by the higher sampling which occurs during such periods of increased cell transmission. Likewise, when a rate reduction occurs, slower arriving cell samples will take much longer to track. Moreover, in the case of FIR type algorithms, unless a negative power of 2 is chosen as the pre-calculated constant xcex2 (see equation (4) above), multiplication is required in computing the algorithm. Likewise, the same problem arises with respect to the constants e and c of equations (15) and (16) above. This imposes constraints on the choice of such constants. Lastly, multiple variables and associated memory space are required on a per connection basis in order to record rate estimation with some of the prior art methods.
The present invention provides an alternative method and apparatus for rate monitoring in a communications network which seeks to alleviate or overcome certain of the disadvantages associated with known rate measurement techniques.
According to a first broad aspect of the present invention there is provided a method of measuring a rate of message element traffic over a message path in a communications network, the message path including at least one connection and being associated with a maximum rate of transmission of message elements thereover, the method comprising the steps of: (a) periodically polling the message path for transmission of a message element, the periodic polling being performed at a polling rate associated with polling intervals which are at least as frequent as the maximum rate of transmission; (b) if transmission of a message element is detected during a said polling interval, incrementing a running count of such detection, the running count of detection being associated with the connection over which the message element was detected; (c) if transmission of a message element is not detected during a said polling interval, incrementing a running count of such non-detection, the running count of non-detection being associated with inactivity of the message path; (d) during each said polling interval, retrieving an oldest stored value from a memory comprising a preselected number of stored values each corresponding respectively to an equal number of most recent sequential events of detection and non-detection resulting from said periodic polling, wherein each stored value which represents an event of detection corresponds to an identifier denoting the connection over which the message element was detected and wherein each stored value which represents an event of non-detection corresponds to an identifier denoting inactivity of the message path; (e) following step (d) and during each said polling interval, decrementing the running count of detection associated with the connection corresponding to the identifier of the retrieved value if the retrieved value represents an event of detection and decrementing the running count of non-detection if the retrieved value represents inactivity of the message path; (f) following step (e) and during each said polling interval, replacing in the memory the retrieved value with a value corresponding to an identifier which denotes the connection over which the message element was detected if transmission of a message element was detected in step (b) and otherwise replacing in the memory the retrieved value with a value corresponding to an identifier which denotes inactivity of the message path if transmission of a message element was not detected in step (c); (g) repeating each of steps (a) through (f) for so long as said measurement is undertaken; and wherein the rate of message element traffic over a connection of the message path is proportional to the running count of detection associated with the connection.
According to a second broad aspect of the present invention there is provided an apparatus for measuring a rate of message element traffic over a message path in a communications network, the message path including at least one connection and being associated with a maximum rate of transmission of message elements thereover, the apparatus comprising: (a) an input port for receiving message elements which are transmitted over the message path; (b) a timer producing a clock rate which is at least as frequent as the maximum rate of transmission; (c) a processor for periodically polling the input port for transmission of a message element, the periodic polling being performed at polling interval which are synchronized to the clock rate of the timer and: (c.1) if transmission of a message element is detected during a polling interval, wherein the processor increments a running count of such detection, the running count of detection being associated with the connection over which the message element was detected; and (c.2) if transmission of a message element is not detected during a polling interval, wherein the processor increments a running count of such non-detection, the running count of non-detection being associated with inactivity of the message path; (d) a memory accessible by said processor and comprising a preselected number of stored values each corresponding respectively to an equal number of most recent sequential events of detection and non-detection resulting from said periodic polling, each stored value which represents an event of detection corresponding to an identifier denoting the connection over which the message element was detected and each stored value which represents an event of non-detection corresponding to an identifier denoting inactivity of the message path, and wherein: (d.1) during each polling interval the processor retrieves an oldest stored value from the memory and decrements the running count of detection associated with the connection corresponding to the identifier of the retrieved value if the retrieved value represents an event of detection and decrements the running count of non-detection if the retrieved value represents inactivity of the message path; (d.2) after decrementing such running count and during the same polling interval, the processor replaces the retrieved value in the memory with a value corresponding to an identifier which denotes the connection over which the message element was detected if transmission of a message element was detected over the input port during the same polling interval and otherwise the processor replaces in the memory the retrieved value with a value corresponding to an identifier which denotes inactivity of the message path if transmission of a message element was not detected over the input port during the same polling interval; and wherein the rate of message element traffic over a connection of the message path is computed proportional to the running count of detection associated with the connection.
According to a third broad aspect of the present invention there is provided a method of measuring a rate of message element traffic over a message path in a communications network, the message path including at least one flow of message element traffic and being associated with a maximum rate of transmission of message elements thereover, the message path being polled periodically for transmission of a message element, the polling being performed at a polling rate associated with polling intervals which are at least as frequent as the maximum rate of transmission, the method comprising the steps of (a) establishing a running count of non-detection of a message element transmitted over the message path, the running count of non-detection representing events of inactivity of the message path for a predetermined number of sequential polling intervals; and (b) for each flow of message element traffic of the message path, establishing a respective ring count of detection of a message element being transmitted therein, each running count of detection representing a number of events of detection of a message element transmitted in a corresponding flow of message element traffic for the predetermined number of sequential polling intervals; and wherein the predetermined number of sequential polling intervals reflects; (b) every polling interval, most recent events of detection and of inactivity of the message path, and wherein the rate of message element traffic in the corresponding flow of message element traffic of the message path for the predetermined number of sequential polling intervals is proportional to the running count of detection for the corresponding flow of message element traffic.